섬 연결하기

📔 문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

📓 제약 조건

섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.

📓 입출력의 예

n	costs	return
4	`[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]`	4

❗ 1번째

이 문제는 최소 코스트를 구하는 문제이고 최소 신장 트리를 구하는 문제이다 아마 이 문제는 크루스칼 알고리즘을 이용하면 풀어 낼 수 있을거같다.

그래프 간선의 비용을 오름차순으로 정렬
낮은 순으로 하나씩 연결
사이클이 형성되면 넘어감
노드 - 1개가 되면 종료

사이클이 같은지 확인할때는 Union - find를 이용해서 부모 노드가 같은경우에는 같은 집합으로 넘어가는 방식으로 한다.

✅ 실행 코드

function get(parent, c) {
  if (parent[c] === c) return c;
  return (parent[c] = get(parent, parent[c]));
}

function union(parent, c1, c2) {
  const n1 = get(parent, c1);
  const n2 = get(parent, c2);
  if (n1 < n2) {
    return (parent[n2] = n1);
  } else {
    return (parent[n1] = n2);
  }
}

function find(parent, c1, c2) {
  const n1 = get(parent, c1);
  const n2 = get(parent, c2);
  return n1 !== n2;
}

function solution(n, costs) {
  let 정답 = 0;
  const parent = Array(n)
    .fill(0)
    .map((x, i) => i);
  costs.sort((a, b) => a[2] - b[2]);

  for (c of costs) {
    if (find(parent, c[0], c[1])) {
      정답 += c[2];
      union(parent, c[0], c[1]);
    }
  }
  return 정답;
}

📚 문제 느낀점

처음에 입출력예 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]으로 4가 나와야하는데 17이 나와서 이게 대체 내가 뭘 잘못짰을까 하고 많이 고민을하면서 하나씩 테스트했는데
union(parent,c[0],c[1])이 union(parent,c[0],[1])으로 들어가서 C1의 값이 계속 1로 고정이 되어서 그랬던것이다.. 이래도 된다는게 신기하네..

이럴때 무한 재귀가 일어나서 터지거나 알고리즘 로직이 깨져서 잘못된 연결을 하고 모든 간선을 이용하게 된다카더라.
1 + 2 + 5 + 1 + 8 = 17

© 문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42861

📔 문제 설명

❗ 1번째

✅ 실행 코드

📚 문제 느낀점

© 문제 출처

© 문제 출처